package leetCode.offer56_ii;

/**
 * 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
 *
 * 示例 1：
 * 输入：nums = [3,4,3,3]
 * 输出：4
 * 示例 2：
 *
 * 输入：nums = [9,1,7,9,7,9,7]
 *
 * 输出：1
 * 限制：
 * 1 <= nums.length <= 10000
 * 1 <= nums[i] < 2^31
 *
 */
public class Solution1 implements Solution{

    /**
     * 解题思路：
     *  每个数字的二进制表示都是： 01010011001这样形式的
     *  数组中相同的数字相同的位上数字是一样的，我们可以先将所有数字的位数相加，
     *  然后再每个位都%3最后相同的数字都会被余掉，留下的就是剩余的一个数字了
     *  例子：
     *  【3，5，3，3】
     *    0011
     *    0101
     *    0011
     *  + 0011
     *  ------------
     *  = 0134
     *
     *    0%3=0
     *    1%3=1
     *    3%3=0
     *    4%3=1
     *    最后结果: 0101 = 5
     *
     * @param nums 输入数组
     * @return
     */
    @Override
    public int singleNumber(int[] nums) {
        int[] counts = new int[32];
        // 执行相加步骤
        for(int num : nums) {
            for(int i=31;i>=0;i--){
                counts[i] += num&1;
                num >>>= 1;
            }
        }
        int res = 0, m = 3;
        for(int i=0;i<32;i++) {
            res <<= 1;
            res |= counts[i]%m;
        }
        return res;
    }

    public static void main(String[] args) {
        Solution1 solution1 = new Solution1();
        int[] param = {3,5,3,3};
        System.out.println(solution1.singleNumber(param));
    }

}
